#include <stdio.h>
#include <omp.h>
#include <time.h>

int max(int a, int b) {
	if(a > b) {
		return a;
	}	
	return b;
}

int min(int a, int b) {
	if(a < b) {
		return a;
	}	
	return b;
}

void swap(int *x,int *y) {
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

/* select the middle one of the randomly selected three elements to 
 	improve the balance between processes. */
int select(int array[], int i, int j, int k) {
	int arrI = array[i], arrJ = array[j], arrK = array[k];
	if(min(arrI,arrK) <= arrJ && arrJ <= max(arrI,arrK)) {
		return j;
	} else if(min(arrK, arrJ) <= arrI && arrI <= max(arrK, arrJ)) {
		return i;
	} else{
		return k;
	}
}

void quicksort(int list[],int m,int n) {
	if( m < n) {
		int size = n-m+1, pivot, i = m+1, j=n, pivot_index;
		
		// get three random indexes from the sublist
		srand(time(NULL));
		int p = rand()%size+m, q = rand()%size+m, r = rand()%size+m;
		
		// select the middle one as pivot
		pivot_index = select(list, p, q, r);
		swap(&list[m],&list[pivot_index]);
		pivot = list[m];
		
		while(i <= j)
		{
			while((i <= n) && (list[i] <= pivot))
				i++;
			while((j >= m) && (list[j] > pivot))
				j--;
			if( i < j)
				swap(&list[i],&list[j]);
		}
		// swap two elements
		swap(&list[m],&list[j]);
		
		// recursively sort the lesser list
		#pragma omp parallel shared(list) num_threads(2) if(n-m>1000)
		{
			#pragma omp sections 
			{
				#pragma omp section 
				quicksort(list,m,j-1);
				
				#pragma omp section 
				quicksort(list,j+1,n);
			}
		}
	}
}

int main(int argc, char* argv[]) {

	// get the size of the array from the user
	int size = 0, i;
	printf("Please enter the size of the array to be sorted: " );
	scanf("%i",  &size );

	//create array with size "size".
	int array[size];
	srand(time(NULL));
	for(i=0; i< size; i++) {
		array[i] = rand();
	}
	
	// output the array before sorting
	for(i=0; i< size; i++) {
		printf("Element %i of the array before sorting= %i\n", i, array[i]);
	}
	omp_set_nested(1);	
	// sort the array in parallel
	quicksort(array, 0, size-1);

	// output the array after sorting
	for(i=0; i< size; i++) {
		printf("Element %i of the array after sorting = %i\n", i, array[i]);
	}
	return 0;
}

	


	
